/**
 * @param {number[]} nums
 * @param {number} i1
 * @param {number} i2
 */
function swap(nums, i1, i2) {
  const temp = nums[i1];
  nums[i1] = nums[i2];
  nums[i2] = temp;
}

/**
 * @description 重新将子节点处理平衡
 * @param {number} child
 * @param {number[]} nums
 * @param {number} length
 */
function resolveChild(child, nums, length) {
  const left = child * 2 + 1;
  const right = left + 1;
  if (left >= length) return;
  const childValue = nums[child];
  const leftValue = nums[left];
  if (right >= length) {
    if (leftValue > childValue) {
      swap(nums, child, left);
    }
    return;
  }
  const rightValue = nums[right];
  if (childValue >= leftValue && childValue >= rightValue) {
    return;
  }
  if (leftValue >= rightValue) {
    swap(nums, child, left);
    resolveChild(left, nums, length);
  } else {
    swap(nums, child, right);
    resolveChild(right, nums, length);
  }
}

/**
 * @description 将指定范围内的树处理为完全二叉树
 * @param {number[]} nums
 * @param {number} length
 */
function completeTree(nums, length) {
  for (let i = Math.floor(length / 2 - 1); i >= 0; i -= 1) {
    resolveChild(i, nums, length);
  }
}

/**
 * @description 堆排（升序）
 * @param {number[]} nums
 */
function heapSort(nums) {
  for (let l = nums.length; l > 1; l -= 1) {
    completeTree(nums, l);
    swap(nums, 0, l - 1);
  }
  return nums;
}

let src;
let answer;
let mine;
try {
  for (let i = 0; i < 1e3; i += 1) {
    const length = Math.floor(1e3 * Math.random());
    src = new Array(length).fill(0);
    for (let j = 0; j < length; j += 1) {
      src[j] = Math.round(1e3 * Math.random());
    }
    answer = [...src];
    answer.sort((a, b) => a - b);
    mine = [...src];
    heapSort(mine);
    if (answer.join() !== mine.join()) {
      throw new Error();
    }
  }
  console.log('测试通过');
} catch (e) {
  console.error('发现错误');
}
